In order to define road geometry that may be utilized for mapping and navigational purposes, probe data may be collected from a variety of probe sources. For example, probe data that identifies the location and heading of a probe source at a particular moment in time may be provided by mobile telephones, such as smart phones, global positioning systems (GPS) that are carried by vehicles and other types of navigation systems. Several different techniques may be employed in order to create road geometry from probe data in instances in which the probe data has a relatively high density and includes relatively high frequency trajectory information.
For example, K-means trajectory clustering associates the trajectories of a cluster of seed points that are spatially close to one another and that have similar headings. However, K-means trajectory clustering generally requires probe data that has low noise and a high probe frequency which results in relatively short distances between probe points in order for the trajectory shape to approximate the road geometry. Another technique is trajectory merging in which probe trajectories are traversed and matching graph edges are merged. Trajectories that do not match existing edges create new edges in the graph. Trajectory merging also requires probe data having relatively low noise and high probe frequency such that there are relatively short distances between probe points in order for the trajectory shape to approximate the road geometry.
A kernel density estimation technique may also be utilized to create road geometry by computing an approximate kernel density estimate of trajectories of probe points or edges over an area of interest. The kernel density estimation technique applies a threshold to produce a binary image of the roads followed by the use of various methods, such as thinning, to produce road centerlines from the binary image. The kernel density estimation technique also requires high density probe data.
Another technique utilizes principal curves. Principal curves describe self-consistent curves that pass through the middle of point data. The principal curves technique may detect individual road segments that require additional logic to address intersections and to create a road network graph. The principal curves technique also requires high probe point density and uniform probe point density to produce the desired results.
As the foregoing techniques illustrate, current techniques for creating road geometry from probe data generally rely on high frequency trajectory information and high density probe data. In instances in which the probe data is sparse and/or noisy, such as in instances in which probe data is captured in a neighborhood in which traffic moves slowly and may be parked for hours at a time in a driveway or along a roadside, the foregoing techniques may be less successful in accurately generating the road geometry.